package com.wtx.chapter09;

/**
 * @description: leetcode 303
 * @author: wtx
 * @createDate: 2020/5/27
 */
public class NumArray {

    private interface Merger<E> {
        E merge(E a, E b);
    }

    private class SegmentTree<E> {

        private E[] tree;   //线段数
        private E[] data;
        private Merger<E> merger;

        public SegmentTree(E[] arr,Merger<E> merger) {
            data = (E[])new Object[arr.length];
            for (int i = 0; i < arr.length; i++)
                data[i] = arr[i];
            tree = (E[]) new Object[4 * arr.length];
            this.merger = merger;
            buildSegmentTree(0,0,data.length-1);
        }

        //在treeIndex的位置创建表示区间为[l...r]的线段树
        private void buildSegmentTree(int treeIndex, int l, int r){

            if (l == r) {
                tree[treeIndex] = data[l];
                return;
            }

            int leftChild = leftChild(treeIndex);
            int rightChild = rightChild(treeIndex);

            int mid = l + (r - l)/2; //不要写成(l + r) / 2，容易导致溢出
            //创建左右孩子结点的线段树
            buildSegmentTree(leftChild,l,mid);
            buildSegmentTree(rightChild,mid+1,r);

            //生成父结点
            tree[treeIndex] = merger.merge(tree[leftChild],tree[rightChild]);
        }

        // 查询 [queryL,queryR]的区间值
        public E query(int queryL, int queryR){

            if (queryL<0 || queryL>=data.length ||
                    queryR<0 || queryR>=data.length || queryL>queryR)
                throw new IllegalArgumentException("index is illegal");

            return query(0,0,data.length-1,queryL,queryR);
        }

        private E query(int treeIndex, int L, int R,int queryL, int queryR){

            if (L == queryL && R == queryR)
                return tree[treeIndex];

            int mid = L + (R-L)/2;
            int leftChild = leftChild(treeIndex);
            int rightChild = rightChild(treeIndex);

            if (queryL >= mid+1)
                return query(rightChild,mid+1,R,queryL,queryR);
            else if (queryR <= mid)
                return query(leftChild,L,mid,queryL,queryR);

            //左右都有
            return merger.merge(query(leftChild,L,mid,queryL,mid),
                    query(rightChild,mid+1,R,mid+1,queryR));
        }

        public int getSize(){
            return data.length;
        }

        public E get( int index ){

            if (index < 0 || index >= data.length)
                throw new IllegalArgumentException("Index is illegal");
            return data[index];
        }

        private int leftChild( int index ){
            return 2*index+1;
        }
        private int rightChild(int index){
            return 2*index+2;
        }
    }

    private SegmentTree<Integer> segmentTree;

    public NumArray(int[] nums) {

        if (nums.length>0){
            Integer[] data = new Integer[nums.length];
            for (int i = 0; i < nums.length; i++)
                data[i] = nums[i];

            segmentTree = new SegmentTree<>(data,(a,b)->a+b);
        }
    }

    public int sumRange(int i, int j) {
        if (segmentTree == null)
            throw new IllegalArgumentException("SegmentTree is null");
        return segmentTree.query(i, j);
    }
}
